In 1734, Đế quốc Nga bắt đầu mở rộng tầm ảnh hưởng tại châu Á bắt đầu từ việc xây dựng một thành phố pháo đài mang tên "Orenburg" tại biên cương phía đông (tại Nam Ural). Vì mục đích này, một khu định cư được lập ra tại đây vào năm 1735 - nơi sông Or và sông Ural gặp nhau.

Địa điểm định cư ban đầu được lựa chọn trong chuyến thám hiểm của I.K. Kirilov, người khởi xướng các hoạt động phát triển trong vùng. Ông lập luận rằng thành phố này là hết sức cần thiết "... trong việc mở các tuyến đường trung chuyển đến Bukhara, Badakhshan, Bulk, và tới Ấn Độ", từ đó có thể thu về vàng bạc châu báu từ những khu vực đó. Sau khi Kirilov qua đời, Vasily Tatishchev trở thành nhân vật tay thế. Ông không coi nơi này thuận tiện cho việc xây dựng thành phố bởi vì liên tục bị ngập lụt vào mùa xuân. Việc này dẫn tới việc chuẩn bị xây dựng một thị trấn mới vào năm 1739 ở hạ lưu sông Ural (Yaik) trên núi Krasnaya (Đỏ). Khu định cư cũ được đặt tên là pháo đài Orsk (nay là thành phố Orsk).

Vào ngày 6 tháng 8 năm 1741, thị trấn mới được thành lập. Tuy nhiên, việc xây dựng chưa bắt đầu. Vị trí trên núi Krasnaya - không có cây cối, địa hình đá và xa sông - cũng không phù hợp để xây dựng thị trấn. Ivan Neplyuyev được bổ nhiệm làm người đứng đầu mới của đoàn thám hiểm Orenburg.

Vào ngày 19 (30) tháng 4 năm 1743, Orenburg được thành lập lần thứ ba, tại khu vực mà trước đó từng là pháo đài Berda, cách vùng núi Krasnogorsk 70 verst (75 km; 46 dặm). Vào mùa hè năm 1742, Neplyuev đích thân chọn một địa điểm mới được bao quanh bởi rừng và các cánh đồng hoa màu, nơi sông Yaik và sông Sakmara hợp lưu. Ngày này nơi đây trở thành trung tâm lịch sử của thành phố. Thành phố được xây dựng trên núi Krasnaya được đặt tên là Krasnogorsk.

Orenburg cuối cùng cũng được thành lập vào năm 1743 bởi Ivan Neplyuyev ở vị trí như ngày nay, cách Orsk khoảng 250 kilômét (160 dặm) về phía tây dọc theo sông Ural. Orenburg là nơi đóng quân tại biên giới với những người Kazakh du mục. Thành phố trở thành trung tâm của người Cossack Orenburg.

Orenburg đóng vai trò trong cuộc khởi nghĩa Pugachev (1773–1774). Vào thời điểm đó, nơi đây là thủ phủ của một khu rộng lớn và là trụ sở của thống đốc. Yemelyan Pugachev bao vây thành phố và pháo đài của nó từ Berda từ tháng 10 năm 1773 tới 26 tháng 3 năm 1774. Việc phòng thủ do trung tướng Ivan Reinsdorf chỉ đạo.[17]Tướng Pyotr Golytsin đánh bại quân của Pugachev tại Berda, và một lần nữa tại Kargala (bắc Orenburg).[18] Phần lớn thành phố chìm trong đổ nát, hàng nghìn cư dân bỏ mạng trong cuộc vây hãm. Các lực lượng chính phủ đập tan quân cách mạng vào cuối năm 1774 dưới sự chỉ đạo của Michelsohn tại Tsaritsyn. Các cuộc trả đũa sau đó chống lại các khu vực phiến quân được do tướng Pyotr Panin cầm đầu.

Pushkin tới thăm Orenburg vào năm 1833 trong chuyến nghiên cứu để lấy ý tưởng cho cuốn Lịch sử Pugachev và tiểu thuyết Người con gái viên đại úy. Tại đây ông gặp Vladimir Dal, người sau này viết cuốn đại từ điển tiếng Nga đầu tiên.

Orenburg là căn cứ của cuộc viễn chinh của tướng Perovsky nhằm tấn công Hãn quốc Khiva từ những năm 1830 tới những năm 1850. Sau cuộc sáp nhập Trung Á vào Đế quốc Nga, Orenburg trở thành một trạm mậu dịch và, kể từ khi có tuyến đường sắt xuyên Aral, Orenburg trở thành một ga đầu mối tới các lãnh thổ Trung Á mới sáp nhập và tới Xibia.

Orenburg là thủ đô của Cộng hòa Xã hội chủ nghĩa Xô viết tự trị Kirghiz (nay là Kazakhstan) thuộc Nga trong giai đoạn 1920–1925. Khi nước cộng hòa này được đổi tên thành Cộng hòa Xã hội chủ nghĩa Xô viết tự trị Kazak vào năm 1925, Orenburg về với Nga và Kyzylorda trở thành thủ đô mới. Almaty trở thành thủ đô mới vào năm 1929 sau khi hoàn thành việc xây dựng tuyến đường sắt Turkestan–Siberia. Cộng hòa Xã hội chủ nghĩa Xô viết tự trị Kazak trở thành một nước cộng hòa liên bang với tên gọi Cộng hòa Xã hội chủ nghĩa Xô viết Kazakh vào năm 1936. Orenburg vẫn tiếp tục là lãnh thổ nước Nga.

Từ năm 1938 tới 1957, thành phố mang tên là Chkalov (Чка́лов) (theo tên phi công Valery Chkalov). Việc thành phố nằm cách xa cuộc xâm lược của Đức Quốc xã trong Chiến tranh thế giới thứ hai dẫn tới việc nhiều doanh nghiệp Liên Xô dời về đây, qua đó giúp thúc đẩy tăng trưởng kinh tế của thành phố.